package kyssion.introductionToAlgorithms.chapter_02;

/**
 * 霍纳规则是一种计算多项式的递归表达式
 * a^x+a^(x-1)+a^(x-2)+....+a 可以表现成 a*(a*(a*(....)+1)+1)+1
 */
public class Alorithms003_2_3_霍纳规则算法 {
    public static void main(String[] args) {
        System.out.println(new Alorithms003_2_3_霍纳规则算法().ans2(2, 3));
    }

    /**
     * 递归的写法
     *
     * @param a
     * @param p
     * @return
     */
    public int ans(int a, int p) {
        if (p == 1) {
            return a + 1;
        }
        return a * ans(a, p - 1) + 1;
    }

    /**
     * 循环写法
     * @param a
     * @param p
     * @return
     */
    public int ans2(int a, int p) {
        int before = 1;
        while (p >= 1) {
            before = before * a + 1;
            p--;
        }
        return before;
    }
}
